package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension.more;

// 编辑距离
// 给你两个单词 word1 和 word2
// 请返回将 word1 转换成 word2 所使用的最少代价
// 你可以对一个单词进行如下三种操作：
// 插入一个字符，代价a
// 删除一个字符，代价b
// 替换一个字符，代价c
// 测试链接 : https://leetcode.cn/problems/edit-distance/
public class Code02_EditDistance {

    public int minDistance(String word1, String word2) {
        //可能性分析
        //还是以 i  j位置结尾分析
        //可能性分析就是穷举法，不能漏掉一些情况
        //   当前 i j位置相等   a: 要  然后找f(i-1,j-1)  可以插入f(i,j-1) 删除f(i-1,j)
        //          不相等     b  替换成本+f(i-1,j-1)   可以插入f(i,j-1) 删除f(i-1,j)
        //
        //return f1(word1.toCharArray(),word2.toCharArray(),word1.length(),word2.length(),1,1,1);
        return f2(word1,word2,1,1,1);
    }

    private int f2(String word1, String word2, int a, int b, int c) {
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        int n = w1.length;
        int m = w2.length;
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i <= m; i++) {
            dp[0][i] = i*a;
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i*b;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                int p1 = Integer.MAX_VALUE;
                //字符相等
                if(w1[i-1]==w2[j-1]){
                    //要
                    p1 = dp[i-1][j-1];
                }
                int p2 = Integer.MAX_VALUE;
                if(w1[i-1]!=w2[j-1]){//替换
                    p2 = dp[i-1][j-1]+c;
                }
                //插入
                int p3 = dp[i][j-1]+a;
                //删除
                int p4 = dp[i-1][j]+b;
                dp[i][j] = Math.min(Math.min(p1,p2),Math.min(p3,p4));
            }
        }
        return dp[n][m];

    }

    // 枚举小优化版
    private int f2Pro(String word1, String word2, int a, int b, int c) {
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        int n = w1.length;
        int m = w2.length;
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i <= m; i++) {
            dp[0][i] = i*a;
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i*b;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                //字符相等
                if(w1[i-1]==w2[j-1]){
                    //要
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j] + b, dp[i][j - 1] + a), dp[i - 1][j - 1] + c);
                }
            }
        }
        return dp[n][m];

    }


    /**
     * 压缩空间
     * @param word1
     * @param word2
     * @param a
     * @param b
     * @param c
     * @return
     */
    private int f3(String word1, String word2, int a, int b, int c) {
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        int n = w1.length;
        int m = w2.length;
        int[] dp = new int[m+1];
        for (int i = 0; i <= m; i++) {
            dp[i] = i*a;
        }
        for (int i = 1; i <=n ; i++) {
            int leftUp = (i-1)*b;
            dp[0] = i*b;
            for (int j = 1; j <=m ; j++) {
                //字符相等
                int temp = dp[j];
                if(w1[i-1]==w2[j-1]){
                    //要
                    dp[j] = leftUp;
                }else{
                    dp[j] = Math.min(Math.min(dp[j] + b, dp[j - 1] + a), leftUp + c);
                }
                leftUp = temp;
            }
        }
        return dp[m];

    }

    /**
     * 可能性分析
     * @param w1
     * @param w2
     * @param i
     * @param j
    // a : str1中插入1个字符的代价
    // b : str1中删除1个字符的代价
    // c : str1中改变1个字符的代价
    // 返回从 str1转化成 str2的最低代价    i j表示长度，为了处理不存在负数的情况
     * @return
     */
    private int f1(char[] w1, char[] w2, int i, int j, int a, int b, int c) {
        //base case
        if(i==0){
            return j*a;
        }
        if(j==0){
            return i*b;
        }
        int p1 = Integer.MAX_VALUE;
        //字符相等
        if(w1[i-1]==w2[j-1]){
            //要
            p1 = f1(w1,w2,i-1,j-1,a,b,c);
        }
        int p2 = Integer.MAX_VALUE;
        if(w1[i-1]!=w2[j-1]){//替换
            p2 = f1(w1,w2,i-1,j-1,a,b,c)+c;
        }
        //插入
        int p3 = f1(w1,w2,i,j-1,a,b,c)+a;
        //删除
        int p4 = f1(w1,w2,i-1,j,a,b,c)+b;
        return Math.min(Math.min(p1,p2),Math.min(p3,p4));
    }

}
